package array;

import java.util.ArrayList;
import java.util.List;

public class ShiftGrid {

    public List<List<Integer>> shiftGrid(int[][] grid, int k) {

        // 把二维grid抽象成一维数组
        int m = grid.length, n = grid[0].length;
        int mn = m * n;
        k = k % mn;
        // 先把最后k个反转
        reverse(grid, mn - k, mn - 1);
        // 然后把前 mn - k 个反转
        reverse(grid, 0, mn - k - 1);
        // 最后把整体反转
        reverse(grid, 0, mn - 1);

        // 转换成Java List
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add(grid[i][j]);
            }
            res.add(row);
        }

        return res;
    }

    /**
     * 通过一维数组的索引访问二维数组
     * @param grid
     * @param index
     * @return
     */
    private int get(int[][] grid, int index) {
        int n = grid[0].length;
        int i = index / n;
        int j = index % n;
        return grid[i][j];
    }

    /**
     * 通过一维数组的索引修改二维数组
     * @param grid
     * @param index
     * @param val
     */
    private void set(int[][] grid, int index, int val) {
        int n = grid[0].length;
        int i = index / n;
        int j = index % n;
        grid[i][j] = val;
    }


    /**
     * 反转一维数组的索引区间内元素
     * @param grid
     * @param i
     * @param j
     */
    private void reverse(int[][] grid, int i, int j) {
        while (i < j) {
            int temp = get(grid, i);
            set(grid, i, get(grid, j));
            set(grid, j, temp);
            i++;
            j--;
        }
    }
}
